`:top
A `!bit array`! (also known as `!bit map`!, `!bit set`!, `!bit string`!, or `!bit vector`!) is an `F33f`_`[array data structure`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Array_data_structure]`_`f that compactly stores `F33f`_`[bits`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bit]`_`f. It can be used to implement a simple `F33f`_`[set data structure`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Set_data_structure]`_`f. A bit array is effective at exploiting `F33f`_`[bit-level parallelism`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bit-level_parallelism]`_`f in hardware to perform operations quickly. A typical bit array stores `*kw`* bits, where `*w`* is the number of bits in the unit of storage, such as a `F33f`_`[byte`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Byte]`_`f or `F33f`_`[word`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Word_(computer_architecture)]`_`f, and `*k`* is some nonnegative integer. If `*w`* does not divide the number of bits to be stored, some space is wasted due to `F33f`_`[internal fragmentation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Fragmentation_(computing)]`_`f.
>>Contents
• `F0af`_`[Definition`#definition]`_`f
• `F0af`_`[Basic operations`#basic-operations]`_`f
• `F0af`_`[More complex operations`#more-complex-operations]`_`f
• `F0af`_`[Population / Hamming weight`#population-hamming-weight]`_`f
• `F0af`_`[Inversion`#inversion]`_`f
• `F0af`_`[Find first one`#find-first-one]`_`f
• `F0af`_`[Compression`#compression]`_`f
• `F0af`_`[Advantages and disadvantages`#advantages-and-disadvantages]`_`f
• `F0af`_`[Applications`#applications]`_`f
• `F0af`_`[Examples`#examples]`_`f
• `F0af`_`[Language support`#language-support]`_`f
• `F0af`_`[See also`#see-also]`_`f
• `F0af`_`[References`#references]`_`f
• `F0af`_`[External links`#external-links]`_`f
-─
>>Definition
A bit array is a mapping from some domain (almost always a range of integers) to values in the set {0, 1}. The values can be interpreted as dark/light, absent/present, locked/unlocked, valid/invalid, et cetera. The point is that there are only two possible values, so they can be stored in one bit. As with other arrays, the access to a single bit can be managed by applying an index to the array. Assuming its size (or length) to be `*n`* bits, the array can be used to specify a subset of the domain (e.g. {0, 1, 2, ..., `*n`*−1}), where a 1-bit indicates the presence and a 0-bit the absence of a number in the set. This set data structure uses about `*n`*/`*w`* words of space, where `*w`* is the number of bits in each `F33f`_`[machine word`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Word_(computer_architecture)]`_`f. Whether the least significant bit (of the word) or the most significant bit indicates the smallest-index number is largely irrelevant, but the former tends to be preferred (on `F33f`_`[little-endian`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Endianness]`_`f machines).
A finite `F33f`_`[binary relation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_relation]`_`f may be represented by a bit array called a `F33f`_`[logical matrix`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Logical_matrix]`_`f. In the `F33f`_`[calculus of relations`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Calculus_of_relations]`_`f, these arrays are composed with `F33f`_`[matrix multiplication`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Matrix_multiplication]`_`f where the arithmetic is Boolean, and such a composition represents `F33f`_`[composition of relations`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Composition_of_relations]`_`f.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]
>>Basic operations
Although most machines are not able to address individual bits in memory, nor have instructions to manipulate single bits, each bit in a word can be singled out and manipulated using `F33f`_`[bitwise operations`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitwise_operation]`_`f. In particular:
Use `B100`F9d9OR`f`b to set a bit to one:
`B100`F9d9 11101010`f`b
`B100`F9d9OR 00000100`f`b
`B100`F9d9 = 11101110`f`b
`B100`F9d9AND`f`b to set a bit to zero:
`B100`F9d9 11101010`f`b
`B100`F9d9AND 11111101`f`b
`B100`F9d9 = 11101000`f`b
`B100`F9d9AND`f`b to determine if a bit is set, by zero-testing:
`B100`F9d9 11101010 11101010`f`b
`B100`F9d9 AND 00000001 AND 00000010`f`b
`B100`F9d9 = 00000000 = 00000010`f`b
`B100`F9d9(=0 ∴ bit isn't set) (≠0 ∴ bit is set)`f`b
`B100`F9d9XOR`f`b to invert or toggle a bit:
`B100`F9d9 11101010 11101110`f`b
`B100`F9d9XOR 00000100 XOR 00000100`f`b
`B100`F9d9 = 11101110 = 11101010`f`b
`B100`F9d9NOT`f`b to invert all bits:
`B100`F9d9NOT 10110010`f`b
`B100`F9d9 = 01001101`f`b
To obtain the `F33f`_`[bit mask`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mask_(computing)]`_`f needed for these operations, we can use a `F33f`_`[bit shift`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitwise_operation]`_`f operator to shift the number 1 to the left by the appropriate number of places, as well as `F33f`_`[bitwise negation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitwise_negation]`_`f if necessary.
Given two bit arrays of the same size representing sets, we can compute their `F33f`_`[union`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Union_(set_theory)]`_`f, `F33f`_`[intersection`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Intersection_(set_theory)]`_`f, and `F33f`_`[set-theoretic difference`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Complement_(set_theory)]`_`f using `*n`*/`*w`* simple bit operations each (2`*n`*/`*w`* for difference), as well as the `F33f`_`[complement`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Signed_number_representations]`_`f of either:
`B100`F9d9for i from 0 to n/w-1`f`b
`B100`F9d9 complement_a[i] := not a[i]`f`b
`B100`F9d9 union[i] := a[i] or b[i]`f`b
`B100`F9d9 intersection[i] := a[i] and b[i]`f`b
`B100`F9d9 difference[i] := a[i] and (not b[i])`f`b
If we wish to iterate through the bits of a bit array, we can do this efficiently using a doubly nested loop that loops through each word, one at a time. Only `*n`*/`*w`* memory accesses are required:
`B100`F9d9for i from 0 to n/w-1`f`b
`B100`F9d9 index := 0 // if needed`f`b
`B100`F9d9 word := a[i]`f`b
`B100`F9d9 for b from 0 to w-1`f`b
`B100`F9d9 value := word and 1 ≠ 0`f`b
`B100`F9d9 word := word shift right 1`f`b
`B100`F9d9 // do something with value`f`b
`B100`F9d9 index := index + 1 // if needed`f`b
Both of these code samples exhibit ideal `F33f`_`[locality of reference`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Locality_of_reference]`_`f, which will subsequently receive large performance boost from a data cache. If a cache line is `*k`* words, only about `*n`*/`*wk`* cache misses will occur.
>>More complex operations
As with `F33f`_`[character strings`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=String_(computer_science)]`_`f it is straightforward to define `*length`*, `*substring`*, `F33f`_`[lexicographical`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lexicographical_order]`_`f `*compare`*, `*concatenation`*, `*reverse`* operations. The implementation of some of these operations is sensitive to `F33f`_`[endianness`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Endianness]`_`f.
>>>Population / Hamming weight
If we wish to find the number of 1 bits in a bit array, sometimes called the population count or Hamming weight, there are efficient branch-free algorithms that can compute the number of bits in a word using a series of simple bit operations. We simply run such an algorithm on each word and keep a running total. Counting zeros is similar. See the `F33f`_`[Hamming weight`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hamming_weight]`_`f article for examples of an efficient implementation.
>>>Inversion
Vertical flipping of a one-bit-per-pixel image, or some FFT algorithms, requires flipping the bits of individual words (so `B100`F9d9b31 b30 ... b0`f`b becomes `B100`F9d9b0 ... b30 b31`f`b). When this operation is not available on the processor, it's still possible to proceed by successive passes, in this example on 32 bits:
`B100`F9d9exchange two 16-bit halfwords`f`b
`B100`F9d9exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)`f`b
`B100`F9d9...`f`b
`B100`F9d9swap bits by pairs`f`b
`B100`F9d9swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)`f`b
`B100`F9d9`f`b
`B100`F9d9The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).`f`b
>>>Find first one
The `F33f`_`[find first set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Find_first_set]`_`f or `*find first one`* operation identifies the index or position of the 1-bit with the smallest index in an array, and has widespread hardware support (for arrays not larger than a word) and efficient algorithms for its computation. When a `F33f`_`[priority queue`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Priority_queue]`_`f is stored in a bit array, find first one can be used to identify the highest priority element in the queue. To expand a word-size `*find first one`* to longer arrays, one can find the first nonzero word and then run `*find first one`* on that word. The related operations `*find first zero`*, `*count leading zeros`*, `*count leading ones`*, `*count trailing zeros`*, `*count trailing ones`*, and `*log base 2`* (see `F33f`_`[find first set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Find_first_set]`_`f) can also be extended to a bit array in a straightforward manner.
>>Compression
A bit array is the most dense storage for "random" bits, that is, where each bit is equally likely to be 0 or 1, and each one is independent. But most data are not random, so it may be possible to store it more compactly. For example, the data of a typical fax image is not random and can be compressed. `F33f`_`[Run-length encoding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Run-length_encoding]`_`f is commonly used to compress these long streams. However, most compressed data formats are not so easy to access randomly; also by compressing bit arrays too aggressively we run the risk of losing the benefits due to bit-level parallelism (`F33f`_`[vectorization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Array_programming]`_`f). Thus, instead of compressing bit arrays as streams of bits, we might compress them as streams of bytes or words (see `F33f`_`[Bitmap index (compression)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitmap_index]`_`f).
>>Advantages and disadvantages
Bit arrays, despite their simplicity, have a number of marked advantages over other data structures for the same problems:
• They are extremely compact; no other data structures can store `*n`* independent pieces of data in `*n`*/`*w`* words.
• They allow small arrays of bits to be stored and manipulated in the register set for long periods of time with no memory accesses.
• Because of their ability to exploit bit-level parallelism, limit memory access, and maximally use the `F33f`_`[data cache`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_cache]`_`f, they often outperform many other data structures on practical data sets, even those that are more asymptotically efficient.
However, bit arrays are not the solution to everything. In particular:
• Without compression, they are wasteful set data structures for sparse sets (those with few elements compared to their range) in both time and space. For such applications, compressed bit arrays, `F33f`_`[Judy arrays`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Judy_array]`_`f, `F33f`_`[tries`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Trie]`_`f, or even `F33f`_`[Bloom filters`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bloom_filter]`_`f should be considered instead.
• Accessing individual elements can be expensive and difficult to express in some languages. If random access is more common than sequential and the array is relatively small, a byte array may be preferable on a machine with byte addressing. A word array, however, is probably not justified due to the huge space overhead and additional cache misses it causes, unless the machine only has word addressing.
>>Applications
Because of their compactness, bit arrays have a number of applications in areas where space or efficiency is at a premium. Most commonly, they are used to represent a simple group of Boolean flags or an ordered sequence of Boolean values.
Bit arrays are used for `F33f`_`[priority queues`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Priority_queue]`_`f, where the bit at index `*k`* is set if and only if `*k`* is in the queue; this data structure is used, for example, by the `F33f`_`[Linux kernel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Linux_kernel]`_`f, and benefits strongly from a find-first-zero operation in hardware.
Bit arrays can be used for the allocation of `F33f`_`[memory pages`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Page_(computing)]`_`f, `F33f`_`[inodes`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Inode]`_`f, disk sectors, etc. In such cases, the term `*bitmap`* may be used. However, this term is frequently used to refer to `F33f`_`[raster images`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Raster_graphics]`_`f, which may use multiple `F33f`_`[bits per pixel`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Color_depth]`_`f.
Another application of bit arrays is the `F33f`_`[Bloom filter`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bloom_filter]`_`f, a probabilistic `F33f`_`[set data structure`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Set_data_structure]`_`f that can store large sets in a small space in exchange for a small probability of error. It is also possible to build probabilistic `F33f`_`[hash tables`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hash_table]`_`f based on bit arrays that accept either false positives or false negatives.
Bit arrays and the operations on them are also important for constructing `F33f`_`[succinct data structures`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Succinct_data_structure]`_`f, which use close to the minimum possible space. In this context, operations like finding the `*n`*th 1 bit or counting the number of 1 bits up to a certain position become important.
Bit arrays are also a useful abstraction for examining streams of `F33f`_`[compressed`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Data_compression]`_`f data, which often contain elements that occupy portions of bytes or are not byte-aligned. For example, the compressed `F33f`_`[Huffman coding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Huffman_coding]`_`f representation of a single 8-bit character can be anywhere from 1 to 255 bits long.
In `F33f`_`[information retrieval`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Information_retrieval]`_`f, bit arrays are a good representation for the posting lists of very frequent terms. If we compute the gaps between adjacent values in a list of strictly increasing integers and encode them using `F33f`_`[unary coding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Unary_coding]`_`f, the result is a bit array with a 1 bit in the `*n`*th position if and only if `*n`* is in the list. The implied probability of a gap of `*n`* is 1/2`*n`*. This is also the special case of `F33f`_`[Golomb coding`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Golomb_coding]`_`f where the parameter M is 1; this parameter is only normally selected when −log(2 − `*p`*) / log(1 − `*p`*) ≤ 1, or roughly the term occurs in at least 38% of documents.
>>Examples
Given a big file of `F33f`_`[IPv4`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=IPv4]`_`f addresses (more than 100 GB) — we need to count unique addresses. If we use generic `B100`F9d9map[string]bool`f`b — we will need more than 64 GB of `F33f`_`[RAM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Random-access_memory]`_`f, so lets use the `!bit map`!, in `F33f`_`[Go`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Go_(programming_language)]`_`f:
`B100`F9d9package main`f`b
`B100`F9d9`f`b
`B100`F9d9import (`f`b
`B100`F9d9 "bufio"`f`b
`B100`F9d9 "fmt"`f`b
`B100`F9d9 "math/bits"`f`b
`B100`F9d9 "os"`f`b
`B100`F9d9)`f`b
`B100`F9d9`f`b
`B100`F9d9// bitsetSize is the number of bytes needed for 2^32 bits (512 MiB)`f`b
`B100`F9d9const bitsetSize = 1 << 29`f`b
`B100`F9d9`f`b
`B100`F9d9func main() {`f`b
`B100`F9d9 file, err := os.Open("ip_addresses")`f`b
`B100`F9d9 if err != nil {`f`b
`B100`F9d9 fmt.Println("Error opening file:", err)`f`b
`B100`F9d9 return`f`b
`B100`F9d9 }`f`b
`B100`F9d9 defer file.Close()`f`b
`B100`F9d9`f`b
`B100`F9d9 bitset := [bitsetSize]byte{}`f`b
`B100`F9d9`f`b
`B100`F9d9 // Use a buffered scanner with a larger buffer`f`b
`B100`F9d9 scanner := bufio.NewScanner(file)`f`b
`B100`F9d9 const maxBuffer = 64 * 1024 // 64 KB buffer`f`b
`B100`F9d9 buf := make([]byte, 0, maxBuffer)`f`b
`B100`F9d9 scanner.Buffer(buf, maxBuffer)`f`b
`B100`F9d9`f`b
`B100`F9d9 // Process each line`f`b
`B100`F9d9 for scanner.Scan() {`f`b
`B100`F9d9 line := scanner.Bytes()`f`b
`B100`F9d9`f`b
`B100`F9d9 // Parse the IP address manually from bytes`f`b
`B100`F9d9 ip := parseIPv4(line)`f`b
`B100`F9d9 // Set the bit`f`b
`B100`F9d9 byteIndex := ip >> 3 // Divide by 8`f`b
`B100`F9d9 bitIndex := ip & 7 // Bit position 0-7`f`b
`B100`F9d9 bitset[byteIndex] |= 1 << bitIndex`f`b
`B100`F9d9 }`f`b
`B100`F9d9`f`b
`B100`F9d9 // Check for scanning errors`f`b
`B100`F9d9 if err := scanner.Err(); err != nil {`f`b
`B100`F9d9 fmt.Println("Error reading file:", err)`f`b
`B100`F9d9 return`f`b
`B100`F9d9 }`f`b
`B100`F9d9`f`b
`B100`F9d9 var count uint64`f`b
`B100`F9d9 for i := 0; i < bitsetSize; i++ {`f`b
`B100`F9d9 count += uint64(bits.OnesCount8(bitset[i]))`f`b
`B100`F9d9 }`f`b
`B100`F9d9`f`b
`B100`F9d9 fmt.Println("Number of unique IPv4 addresses:", count)`f`b
`B100`F9d9}`f`b
`B100`F9d9`f`b
`B100`F9d9func parseIPv4(line []byte) (ip uint32) {`f`b
`B100`F9d9 i := 0`f`b
`B100`F9d9`f`b
`B100`F9d9 // Octet 1`f`b
`B100`F9d9 n := uint32(line[i] - '0')`f`b
`B100`F9d9 for i = 1; line[i] != '.'; i++ {`f`b
`B100`F9d9 n = n*10 + uint32(line[i]-'0')`f`b
`B100`F9d9 }`f`b
`B100`F9d9 ip |= n << 24`f`b
`B100`F9d9 i++ // Skip the dot`f`b
`B100`F9d9`f`b
`B100`F9d9 // Octet 2`f`b
`B100`F9d9 n = uint32(line[i] - '0')`f`b
`B100`F9d9 i++`f`b
`B100`F9d9 for ; line[i] != '.'; i++ {`f`b
`B100`F9d9 n = n*10 + uint32(line[i]-'0')`f`b
`B100`F9d9 }`f`b
`B100`F9d9 ip |= n << 16`f`b
`B100`F9d9 i++ // Skip the dot`f`b
`B100`F9d9`f`b
`B100`F9d9 // Octet 3`f`b
`B100`F9d9 n = uint32(line[i] - '0')`f`b
`B100`F9d9 i++`f`b
`B100`F9d9 for ; line[i] != '.'; i++ {`f`b
`B100`F9d9 n = n*10 + uint32(line[i]-'0')`f`b
`B100`F9d9 }`f`b
`B100`F9d9 ip |= n << 8`f`b
`B100`F9d9 i++ // Skip the dot`f`b
`B100`F9d9`f`b
`B100`F9d9 // Octet 4`f`b
`B100`F9d9 n = uint32(line[i] - '0')`f`b
`B100`F9d9 i++`f`b
`B100`F9d9 for ; i < len(line); i++ {`f`b
`B100`F9d9 n = n*10 + uint32(line[i]-'0')`f`b
`B100`F9d9 }`f`b
`B100`F9d9 ip |= n`f`b
`B100`F9d9`f`b
`B100`F9d9 return ip`f`b
`B100`F9d9}`f`b
>>Language support
The `F33f`_`[APL programming language`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=APL_(programming_language)]`_`f fully supports bit arrays of arbitrary shape and size as a Boolean datatype distinct from integers. All major implementations (`F33f`_`[Dyalog APL, APL2, APL Next, NARS2000, Gnu APL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=APL_(programming_language)]`_`f, etc.) pack the bits densely into whatever size the machine word is. Bits may be accessed individually via the usual indexing notation (A[3]) as well as through all of the usual primitive functions and operators where they are often operated on using a special case algorithm such as summing the bits via a table lookup of bytes.
The `F33f`_`[C programming language`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=C_(programming_language)]`_`f's `*`F33f`_`[bit fields`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bit_field]`_`f`*, pseudo-objects found in structs with size equal to some number of bits, are in fact small bit arrays; they are limited in that they cannot span words. Although they give a convenient syntax, the bits are still accessed using bytewise operators on most machines, and they can only be defined statically (like C's static arrays, their sizes are fixed at compile-time). It is also a common idiom for C programmers to use words as small bit arrays and access bits of them using bit operators. A widely available header file included in the `F33f`_`[X11`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=X11]`_`f system, xtrapbits.h, is “a portable way for systems to define bit field manipulation of arrays of bits.” A more explanatory description of aforementioned approach can be found in the comp.lang.c faq.
In `F33f`_`[C++`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=C++]`_`f, although individual `B100`F9d9bool`f`bs typically occupy the same space as a byte or an integer, the `F33f`_`[STL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Standard_Template_Library]`_`f type `B100`F9d9vector<bool>`f`b is a `F33f`_`[partial template specialization`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Partial_template_specialization]`_`f in which bits are packed as a space efficiency optimization. Since bytes (and not bits) are the smallest addressable unit in C++, the [] operator does `*not`* return a reference to an element, but instead returns a `F33f`_`[proxy reference`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Proxy_pattern]`_`f. This might seem a minor point, but it means that `B100`F9d9vector<bool>`f`b is `*not`* a standard STL container, which is why the use of `B100`F9d9vector<bool>`f`b is generally discouraged. Another unique STL class, `B100`F9d9bitset`f`b,`:cite-ref-c-2-0[`F5bf`_`[2`#cite-note-c-2]`_`f] creates a vector of bits fixed at a particular size at compile-time, and in its interface and syntax more resembles the idiomatic use of words as bit sets by C programmers. It also has some additional power, such as the ability to efficiently count the number of bits that are set. The `F33f`_`[Boost C++ Libraries`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boost_C++_Libraries]`_`f provide a `B100`F9d9dynamic_bitset`f`b class`:cite-ref-boost-3-0[`F5bf`_`[3`#cite-note-boost-3]`_`f] whose size is specified at run-time.
The `F33f`_`[D programming language`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=D_programming_language]`_`f provides bit arrays in its standard library, Phobos, in `B100`F9d9std.bitmanip`f`b. As in C++, the [] operator does not return a reference, since individual bits are not directly addressable on most hardware, but instead returns a `B100`F9d9bool`f`b.
In `F33f`_`[Java`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Java_(programming_language)]`_`f, the class `B100`F9d9BitSet`f`b creates a bit array that is then manipulated with functions named after bitwise operators familiar to C programmers. Unlike the `B100`F9d9bitset`f`b in C++, the Java `B100`F9d9BitSet`f`b does not have a "size" state (it has an effectively infinite size, initialized with 0 bits); a bit can be set or tested at any index. In addition, there is a class `B100`F9d9EnumSet`f`b, which represents a Set of values of an `F33f`_`[enumerated type`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Enumerated_type]`_`f internally as a bit vector, as a safer alternative to bit fields.
The `F33f`_`[.NET Framework`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=.NET_Framework]`_`f supplies a `B100`F9d9BitArray`f`b collection class. It stores bits using an array of type `B100`F9d9int`f`b (each element in the array usually represents 32 bits).`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f] The class supports random access and bitwise operators, can be iterated over, and its `B100`F9d9Length`f`b property can be changed to grow or truncate it.
Although `F33f`_`[Standard ML`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Standard_ML]`_`f has no support for bit arrays, Standard ML of New Jersey has an extension, the `B100`F9d9BitArray`f`b structure, in its SML/NJ Library. It is not fixed in size and supports set operations and bit operations, including, unusually, shift operations.
`F33f`_`[Haskell`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Haskell_(programming_language)]`_`f likewise currently lacks standard support for bitwise operations, but both `F33f`_`[GHC`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Glasgow_Haskell_Compiler]`_`f and Hugs provide a `B100`F9d9Data.Bits`f`b module with assorted bitwise functions and operators, including shift and rotate operations and an "unboxed" array over Boolean values may be used to model a Bit array, although this lacks support from the former module.
In `F33f`_`[Perl`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Perl]`_`f, strings can be used as expandable bit arrays. They can be manipulated using the usual bitwise operators (`B100`F9d9~ | & ^`f`b),`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f] and individual bits can be tested and set using the `*vec`* function.`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f]
In `F33f`_`[Ruby`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Ruby_(programming_language)]`_`f, you can access (but not set) a bit of an integer (`B100`F9d9Fixnum`f`b or `B100`F9d9Bignum`f`b) using the bracket operator (`B100`F9d9[]`f`b), as if it were an array of bits.
Apple's `F33f`_`[Core Foundation`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Core_Foundation]`_`f library contains CFBitVector and CFMutableBitVector structures.
`F33f`_`[PL/I`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PL/I]`_`f supports arrays of `*bit strings`* of arbitrary length, which may be either fixed-length or varying. The array elements may be `*aligned`*— each element begins on a byte or word boundary— or `*unaligned`*— elements immediately follow each other with no padding.
`F33f`_`[PL/pgSQL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PL/pgSQL]`_`f and PostgreSQL's SQL support `*bit strings`* as native type. There are two SQL bit types: `B100`F9d9bit(`*`B100`F9d9n`f`b`*)`f`b and `B100`F9d9bit varying(`*`B100`F9d9n`f`b`*)`f`b, where `*`B100`F9d9n`f`b`* is a positive integer.`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f]
Hardware description languages such as `F33f`_`[VHDL`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=VHDL]`_`f, `F33f`_`[Verilog`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Verilog]`_`f, and `F33f`_`[SystemVerilog`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SystemVerilog]`_`f natively support bit vectors as these are used to model storage elements like `F33f`_`[flip-flops`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Flip-flop_(electronics)]`_`f, hardware busses and hardware signals in general. In hardware verification languages such as OpenVera, `F33f`_`[e`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=E_(verification_language)]`_`f and `F33f`_`[SystemVerilog`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=SystemVerilog]`_`f, bit vectors are used to sample values from the hardware models, and to represent data that is transferred to hardware during simulations.
`F33f`_`[Common Lisp`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Common_Lisp]`_`f provides multi-dimensional bit arrays. A one-dimensional `B100`F9d9bit-vector`f`b implementation is provided as a special case of the built-in `B100`F9d9array`f`b, acting in a dual capacity as a class and a type specifier.`:cite-ref-8[`F5bf`_`[8`#cite-note-8]`_`f] Bit arrays (and thus bit vectors) relies on the general `B100`F9d9make-array`f`b function to be configured with an element type of `B100`F9d9bit`f`b, which optionally permits a bit vector to be designated as dynamically resizable. The `B100`F9d9bit-vector`f`b, however, is not infinite in extent. A more restricted `B100`F9d9simple-bit-vector`f`b type exists, which explicitly excludes the dynamic characteristics.`:cite-ref-9[`F5bf`_`[9`#cite-note-9]`_`f] Bit vectors are represented as, and can be constructed in a more concise fashion by, the `*reader macro`* `B100`F9d9#*`*bits`*`f`b.`:cite-ref-10[`F5bf`_`[10`#cite-note-10]`_`f] In addition to the general functions applicable to all arrays, dedicated operations exist for bit arrays. Single bits may be accessed and modified using the `B100`F9d9bit`f`b and `B100`F9d9sbit`f`b functions`:cite-ref-11[`F5bf`_`[11`#cite-note-11]`_`f] and an extensive number of logical operations is supported.`:cite-ref-12[`F5bf`_`[12`#cite-note-12]`_`f]
>>See also
• `F33f`_`[Arithmetic logic unit`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Arithmetic_logic_unit]`_`f
• `F33f`_`[Binary code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_code]`_`f
• `F33f`_`[Binary numeral system`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_numeral_system]`_`f
• `F33f`_`[Bitboard`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitboard]`_`f Chess and similar games.
• `F33f`_`[Bit field`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bit_field]`_`f
• `F33f`_`[Bit mask`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Mask]`_`f
• `F33f`_`[Bitmap index`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitmap_index]`_`f
• `F33f`_`[Bitstream`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bitstream]`_`f
• `F33f`_`[Finite field`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Finite_field]`_`f of 2 elements, or `F33f`_`[GF(2)`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=GF(2)]`_`f
• `F33f`_`[Judy array`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Judy_array]`_`f
• `F33f`_`[Variable-length code`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Variable-length_code]`_`f
>>References
`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `F33f`_`[Irving Copilowish`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Irving_Copilowish]`_`f (December 1948) "Matrix development of the calculus of relations", `F33f`_`[Journal of Symbolic Logic`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Journal_of_Symbolic_Logic]`_`f 13(4): 193–203 Jstor link
`:cite-note-c-2`!2.`! `F0af`_`[↑`#cite-ref-c-2-0]`_`f "SGI.com Tech Archive Resources now retired". `F33f`_`[SGI`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Silicon_Graphics]`_`f. 2 January 2018.
`:cite-note-boost-3`!3.`! `F0af`_`[↑`#cite-ref-boost-3-0]`_`f "dynamic_bitset<Block, Allocator> - 1.66.0". `*www.boost.org`*.
`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f ".NET mscorlib source code". `*github.com/microsoft`*. 15 October 2021.
`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f "perlop - perldoc.perl.org". `*perldoc.perl.org`*.
`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f "vec - perldoc.perl.org". `*perldoc.perl.org`*.
`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f "8.10. Bit String Types". 30 September 2021.
`:cite-note-8`!8.`! `F0af`_`[↑`#cite-ref-8]`_`f "CLHS: System Class BIT-VECTOR". `*www.lispworks.com`*.
`:cite-note-9`!9.`! `F0af`_`[↑`#cite-ref-9]`_`f "CLHS: Type SIMPLE-BIT-VECTOR". `*www.lispworks.com`*.
`:cite-note-10`!10.`! `F0af`_`[↑`#cite-ref-10]`_`f "CLHS: Section 2.4.8.4". `*www.lispworks.com`*.
`:cite-note-11`!11.`! `F0af`_`[↑`#cite-ref-11]`_`f "CLHS: Accessor BIT, SBIT". `*www.lispworks.com`*.
`:cite-note-12`!12.`! `F0af`_`[↑`#cite-ref-12]`_`f "CLHS: Function BIT-AND, BIT-ANDC1, BIT-ANDC2..." `*www.lispworks.com`*.
>>External links
• mathematical bases Archived 2019-10-16 at the `F33f`_`[Wayback Machine`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Wayback_Machine]`_`f by Pr. D.E.Knuth
• vector<bool> Is Nonconforming, and Forces Optimization Choice
• vector<bool>: More Problems, Better Solutions
`c`F0af`_`[↑ Back to top`#top]`_`f`a